//不允许 用 '/' 和 '%'
//减法代替除法 倍增减数来提高效率
#include <cmath>
class Solution
{
public:
    int divide(int A, int B)
    {
        long long num = 0;
        long long a = A;
        long long b = B;
        bool is_b_n = b < 0 ? true : false;
        bool is_a_n = a < 0 ? true : false;
        long long max = pow(2, 31) - 1;
        long long min = pow(2, 32);
        min *= -1;
        if (is_b_n)
        {
            b *= -1;
        }
        if (is_a_n)
        {
            a *= -1;
        }
        while (a >= b)
        {
            long long temp = b;
            unsigned int count = 1; // a的绝对值大于b的 那么肯定a能减一次b
            while (a >= temp + temp)
            {
                count += count; // 可以减的次数翻倍
                temp += temp;   // 减数也翻倍
            }
            num += count;
            a -= temp;
        }
        if (is_a_n != is_b_n)
            num *= -1;
        if (num > max)
        {
            num = max;
        }
        if (num < min)
        {
            num = min;
        }

        return num;
    }
};